﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.AccessControl;
using System.Text;
using System.Threading.Tasks;

namespace ZuoAlgorithms.Class024;

// 无序数组中第K大的元素
// 测试链接 : https://leetcode.cn/problems/kth-largest-element-in-an-array/
public  class RandomizedSelect
{
    // 随机选择算法，时间复杂度O(n)
    public static int FindKthLargest(int[] arr, int k)
    {
        return RandomizedSelected(arr, arr.Length - k);
    }

    // 如果arr排序的话，在i位置的数字是什么
    public static int RandomizedSelected(int[] arr, int i)
    {
        int res = 0;
        for (int l = 0, r = arr.Length - 1; l <= r;)
        {
            // 随机这一下，常数时间比较大
            // 但只有这一下随机，才能在概率上把时间复杂度收敛到O(n)
            Random rand = new Random();
            Partition(arr,l,r,arr[l +(int)(rand.Next()*(r-l +1))]);
            // 因为左右两侧只需要走一侧
            // 所以不需要临时变量记录全局的first、last
            // 直接用即可
            if (i < first)
            {
                r = first - 1;
            }
            else if (i > last)
            {
                l = last + 1;
            }
            else
            {
                res = arr[i];
                break;
            }
        }
        return res;
    }
    
    
    // 荷兰国旗问题
    public static int first, last;
    public static void Partition(int[] arr, int left, int right, int x)
    {
        first = left;
        last = right;
        int i = left;
        while (left <= last)
        {
            if (arr[last] == x)
            {
                x++;
            }
            else if (arr[i] < x)
            {
                Swap(arr, first++, i++);
            }
            else
            {
                Swap(arr, i, last--);
            }
        }
    }

  
    public static void Swap(int[] arr, int left, int right)
    {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
}
